翻訳と辞書 Words near each other ・ Diyarbakır Atatürk Stadium ・ Diyarbakır Fortress ・ Diyarbakır oil field ・ Diyarbakır Prison ・ Diyarbakır Province ・ Diyarbakır Stadium ・ Diyarbakırspor ・ Diyarbekir Eyalet ・ Diyarbekir Vilayet ・ Diyari ・ Diyari language ・ Diyatalawa ・ Dixon Ward ・ Dixon Waterfowl Refuge ・ Dixon's Chimney and Shaddon Mill ・ Dixon's factorization method ・ Dixon's Ferry ・ Dixon's identity ・ Dixon's Q test ・ Dixon's Return ・ Dixon, California ・ Dixon, Illinois ・ Dixon, Indiana ・ Dixon, Iowa ・ Dixon, Kentucky ・ Dixon, Missouri ・ Dixon, Montana ・ Dixon, Nebraska ・ Dixon, New Mexico ・ Dixon, New Orleans Dictionary Lists mini英和辞書 mini和英辞書 Webster 1913 Latin-English FOLDOC Wikipedia English ウィキペディア

翻訳と辞書　辞書検索 [ 開発暫定版 ] スポンサード リンク Dixon's factorization method ： ウィキペディア英語版 Dixon's factorization method In number theory, Dixon's factorization method (also Dixon's random squares method or Dixon's algorithm) is a general-purpose integer factorization algorithm; it is the prototypical factor base method. Unlike for other factor base methods, its run-time bound comes with a rigorous proof that does not rely on conjectures about the smoothness properties of the values taken by polynomial. The algorithm was designed by John D. Dixon, a mathematician at Carleton University, and was published in 1981. ==Basic idea== Dixon's method is based on finding a congruence of squares modulo the integer N which we intend to factor. Fermat's factorization algorithm finds such a congruence by selecting random or pseudo-random ''x'' values and hoping that the integer ''x''2 mod N is a perfect square (in the integers): :$x^2\backslash equiv\; y^2\backslash quad(\backslash hboxN),\backslash qquad\; x\backslash not\backslash equiv\backslash pm\; y\backslash quad(\backslash hboxN).$ For example, if , we notice (by starting at 292, the first number greater than and counting up) that is 256, the square of 16. So . Computing the greatest common divisor of and ''N'' using Euclid's algorithm gives us 163, which is a factor of ''N''. In practice, selecting random ''x'' values will take an impractically long time to find a congruence of squares, since there are only squares less than ''N''. Dixon's method replaces the condition "is the square of an integer" with the much weaker one "has only small prime factors"; for example, there are 292 squares smaller than 84923; 662 numbers smaller than 84923 whose prime factors are only 2,3,5 or 7; and 4767 whose prime factors are all less than 30. (Such numbers are called ''B-smooth'' with respect to some bound ''B''.) If we have lots of numbers $a\_1\; \backslash ldots\; a\_n$ whose squares can be factorized as $a\_i^2\; \backslash mod\; N\; =\; \backslash prod\_^m\; b\_j^$ will give us a subset of the $a\_i$ whose squares combine to a product of small primes to an even power — that is, a subset of the $a\_i$ whose squares multiply to the square of a (hopefully different) number mod N. 抄文引用元・出典: フリー百科事典『 ウィキペディア（Wikipedia）』 ■ウィキペディアで「Dixon's factorization method」の詳細全文を読む スポンサード リンク 翻訳と辞書 : 翻訳のためのインターネットリソース Copyright(C) kotoba.ne.jp 1997-2016. All Rights Reserved.